package com.lfg.leetcode.leetcode200;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class No212findWords {

    public static void main(String[] args) {
        List<String> ret = findWords(new char[][]{
                new char[]{'o', 'a', 'a', 'n'},
                new char[]{'e', 't', 'a', 'e'},
                new char[]{'i', 'h', 'k', 'r'},
                new char[]{'i', 'f', 'l', 'v'}
        }, new String[]{"eat", "oath"});


        for (String i : ret) {
            System.out.println(i);
        }
    }


    public static List<String> findWords(char[][] board, String[] words) {
        List<String> ret = new ArrayList<>();

        if (words.length == 0) {
            return ret;
        }
        if (board.length == 0) {
            return ret;
        }
        if (board[0].length == 0) {
            return ret;
        }

        TrieNode root = new TrieNode();
        for (String word : words) {
            addWord(root, word);
        }
        Set<String> set = new HashSet<>();
        boolean[][] visit = new boolean[board.length][board[0].length];
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                dfs(board, i, j, set, visit, str, root);
            }
        }
        ret.addAll(set);
        return ret;
    }

    public static void dfs(char[][] board, int i, int j, Set<String> ret, boolean[][] visit, StringBuilder str, TrieNode node) {
        if (node == null) {
            return;
        }

        if (i < 0 || i >= board.length) {
            return;
        }
        if (j < 0 || j >= board[0].length) {
            return;
        }
        if (visit[i][j]) {
            return;
        }
        char c = board[i][j];
        int index = c - 'a';
        if (index > 26) {
            return;
        }
        visit[i][j] = true;
        TrieNode child = node.children[index];
        str.append(c);
        if (null != child) {
            if (child.cnt > 0) {
                ret.add(str.toString());
            }
            dfs(board, i + 1, j, ret, visit, str, child);
            dfs(board, i - 1, j, ret, visit, str, child);
            dfs(board, i, j + 1, ret, visit, str, child);
            dfs(board, i, j - 1, ret, visit, str, child);
        }
        visit[i][j] = false;
        str.deleteCharAt(str.length() - 1);
    }

    public static void addWord(TrieNode root, String word) {
        TrieNode e = root;
        for (int i = 0; i < word.length(); i++) {
            int pos = word.charAt(i) - 'a';
            TrieNode child = e.children[pos];
            if (null == child) {
                child = new TrieNode();
                e.children[pos] = child;
                e.childrenLen++;
                child.val = word.charAt(i);
            }
            e = child;
        }
        e.cnt++;
    }

    static class TrieNode {
        char val;
        TrieNode children[] = new TrieNode[26];
        int childrenLen;
        int cnt;
    }

}
